package com.wenhao.leetcode.hard;

import java.util.*;

/**
 * 题目：https://leetcode-cn.com/problems/create-maximum-number/
 * 拼接最大数
 *
 * 靠！这一题归并的时候还不可以直接像归并排序里面一样，要比较剩余的所有值的大小才可以
 *
 * 这个代码今天晚上重新写一下
 * 别他妈用LinkedList做栈了，直接用数组不香吗
 *
 * @author Wenhao Tong
 * @date 2021/7/10 下午2:07
 */
public class LeetCode321 {
    public static void main(String[] args) {
        LeetCode321 leetCode321 = new LeetCode321();
        int[] result = leetCode321.maxNumber(new int[]{6,7},new int[]{6,0,4},5);
        for (int i : result) {
            System.out.print(i);
        }
    }
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        Map<Integer,int[]> map = new HashMap<>();
        int max = 0;
        int length = nums1.length + nums2.length;
        for (int i = 0;i <= length - k;i++) {
            Deque<Integer> stack1 = removeKdigits(nums1,i);
            Deque<Integer> stack2 = removeKdigits(nums2,length - k - i);
            int[] result = new int[k];
            int value = 0;
            for (int j = 0;j < k;j++) {
                if (stack1.size() != 0 && stack2.size() != 0){
                    result[j] = stack1.peekLast() > stack2.peekLast() ? stack1.pollLast() : stack2.pollLast();
                } else {
                    result[j] = stack1.size() == 0 ? stack2.pollLast() : stack1.pollLast();
                }
                value = value * 10 + result[j];
            }
            max = value > max ? value : max;
            map.put(value,result);
        }
        return map.get(max);
    }

    private Deque<Integer> removeKdigits (int[] nums, int k) {
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0;i < nums.length;i++) {
            while (stack.size() > 0 && nums[i] > stack.peek() && k > 0) {
                stack.pop();
                k--;
            }
            stack.push(nums[i]);
        }
        while (stack.size() > nums.length - k) {
            stack.pop();
        }
        return stack;
    }

    // 比较 nums1[i,m)  和 nums2[j, n)
    // nums1 != null && nums2 != null
    private int compare(int[] nums1, int i, int[] nums2, int j){
        int m = nums1.length;
        int n = nums2.length;

        for(int k=0, limit = Math.min(m-i, n-j); k < limit; k++){
            if(nums1[i + k] != nums2[j + k])    return Integer.compare(nums1[i + k], nums2[j + k]);
        }

        return Integer.compare(m - i, n - j);
    }

}
